#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
#define error 0
#define ok 1

// typedef struct {
//     int num;
// }stu;
typedef struct student{
    int data;
    struct student *next;
}lnote,*linklist;

//初始化链表
void initlink(linklist *l)
{
    //创建头结点，为头结点分配内存
    *l = (linklist)malloc(sizeof(lnote));
    //令头节点的指针为空指针
    (*l)->next = NULL;
}
//判断链表是否为空
bool emptylint(linklist l)
{
    if(l->next) return false;
    return true;
}
//清空链表
void clearlist(linklist *l)
{
    linklist p,q;
    //将第一个节点赋值给p
    p = (*l)->next;
    while(p)
    {
        q = p->next;
        free(p);
        p = q;
    }//将下一个节点赋值给q，释放q，将q赋值给q
    (*l)->next = NULL;
}
//返回链表长度
int lengthlist(linklist l)
{
    int cnt = 0;
    linklist p;
    //声明一个节点指针 p 指向链表的首元节点
    p = l->next;
    while(p)
    {
        cnt++;
        p = p->next;
    }//当 p 不为空时，使指针 p 不断后移，兵=并且计数器计数
    return cnt;
}
//获取链表第i个元素
int getelem(linklist l,int i,int *e)
{
    //创建一个节点指针p指向链表的第一个节点，计数器初始化为1
    int j=1;
    linklist p = l->next;
    while(p&&j<i)
    {   
        p = p->next;
        j++;
    }//遍历链表，使p的指针不断后移
    if(!p||i<j) return error;//如果链表末尾p为空，则说明第i个元素不存在
    else if(i==j){
        *e = p->data;
    }
    return ok;
}
//按值查找元素
int findelem(linklist l,int e)
{
    //按值查找
    int i = 0;
    linklist p;
    p = l->next;
    while(p)
    {
        i++;
        if(memcmp(&p->data,&e,sizeof(lnote)))//判断结构体字符串是否相等
        {
            return i;
        }
        p = p->next;
    }
    return 0;
}
//插入元素
void insertelem(linklist *l,int i,int e)
{
    linklist p,s;
    p = (*l);
    int j = 0;
    while(p&&j<(i-1))
    {
        j++;
        p = p->next;
    }//先寻找目标位置
    if(!p||(j>i-1)) return;
    s = (linklist)malloc(sizeof(lnote));//生成新结点
    s->data = e;//数据传入
    s->next = p->next;//将新结点*s的指针域指向结点p
    p->next = s;//将结点*p的指针域指向新结点*s
}
//删除元素
void deletelem(linklist *l,int i)
{
    //声明一节点 p 指向链表的头结点，计数器初始化为0
    linklist p,q;
    int j=0;
    p = (*l);
    while(p->next&&(j<i-1))
    {
        p = p->next;
        j++;
    }//先查找到i元素的位置
    if(!p||(j>i-1)) return;//判断是否合法化
    q = p->next;//将要删除的节点赋值给 q
    p->next = q->next;//改变删除结点前驱结点的指针域
    free(q);
}
//遍历输出链表
int traverlist(linklist l)
{
    linklist p = l->next;
    while(p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    return ok; 
}
//链表的创建(头插法)
void creatlisthead(linklist *l,int n)
{
    linklist p;
    //建立一个带头结点的链表
    initlink(&p);
    for(int i=n;i>0;i--)
    {
        p = (linklist)malloc(sizeof(lnote));//每次建立新结点
        scanf("%d",&p->data); //输入元素值赋给新结点*p的数据域
        p->next = (*l)->next;//将p节点的指针指向头结点后面的节点
        (*l)->next = p;//将节点 p 插入到表头
    }
}
//链表的创建(尾插法)
void creatlistlast(linklist *l,int n)
{
    linklist r,p;
    initlink(&p);
    r = (*l);
    for(int i=n;i>0;i--)
    {
        p = (linklist)malloc(sizeof(lnote));
        scanf("%d",&p->data);
        r->next = p;
        r = p;
    }
    r->next = NULL;
}

//主循环
int main(int argc,char const *argv[])
{
    linklist l;
    printf("------构造一个空的链表L------\n");
    initlink(&l);
    printf("链表长度为:%d \n",lengthlist(l));

    creatlisthead(&l,5);
    printf("链表长度为:%d \n",lengthlist(l));
    traverlist(l);
    int r = emptylint(l);
    printf("L是否为空：r = %d (1:是 0:否) \n",r);
    
    int e,i;
    scanf("%d%d",&i,&e);
    insertelem(&l,i,e);
    printf("在链表的第%d个位置插入%d \n",i,e);
    printf("在第%d个位置插入新元素%d后，链表长度为:%d \n",i,e,lengthlist(l));
    traverlist(l);

    int ii;
    scanf("%d",&ii);
    deletelem(&l,ii);
    printf("删除第%d个元素后，链表长度为:%d \n",ii,lengthlist(l));
    traverlist(l);

    getelem(l,5,&e);
    printf("您查询的元素值为%d\n",e);
    
    clearlist(&l);
	printf("清空L后，Length(l) = %d \n",lengthlist(l));
	r = emptylint(l);
	printf("L是否为空：r = %d (1:是 0:否) \n",r);

    printf("重新生成一个新链表\n");
    creatlistlast(&l,5);
    printf("链表长度为:%d \n",lengthlist(l));
    traverlist(l);
    r = emptylint(l);
    printf("L是否为空：r = %d (1:是 0:否) \n",r);

    clearlist(&l);
	printf("清空L后，Length(l) = %d \n",lengthlist(l));
	r = emptylint(l);
	printf("L是否为空：r = %d (1:是 0:否) \n",r);
    return 0;
}